HackerRank Knapsack - 競プロ

HackerRank Knapsack

https://www.hackerrank.com/challenges/unbounded-knapsack/problem

提出

code: python

import math

import os

import random

import re

import sys

#

# Complete the 'unboundedKnapsack' function below.

#

# The function is expected to return an INTEGER.

# The function accepts following parameters:

# 1. INTEGER k

# 2. INTEGER_ARRAY arr

#

def unboundedKnapsack(k, arr):

# Write your code here

dp = False * k

arr.sort()

dp[arr0] = True

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

t = int(input().strip())

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input0)

k = int(first_multiple_input1)

arr = list(map(int, input().rstrip().split()))

result = unboundedKnapsack(k, arr)

fptr.write(str(result) + '\n')

fptr.close()

解答

code: python

import math

import os

import random

import re

import sys

#

# Complete the 'unboundedKnapsack' function below.

#

# The function is expected to return an INTEGER.

# The function accepts following parameters:

# 1. INTEGER k

# 2. INTEGER_ARRAY arr

#

def unboundedKnapsack(k, arr):

# Write your code here

dp = False * (k+1)

dp0 = True

for v in arr:

for i in range(k+1):

if dpi and i+v <= k:

dpi+v = True

for i in range(k, -1, -1):

if dpi:

return i

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

t = int(input().strip())

while t:

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input0)

k = int(first_multiple_input1)

arr = list(map(int, input().rstrip().split()))

result = unboundedKnapsack(k, arr)

fptr.write(str(result) + '\n')

t -= 1

fptr.close()

テーマ

メモ

https://www.youtube.com/watch?v=NCuLE3-Lu0k

提出

code: python

import math

import os

import random

import re

import sys

#

# Complete the 'unboundedKnapsack' function below.

#

# The function is expected to return an INTEGER.

# The function accepts following parameters:

# 1. INTEGER k

# 2. INTEGER_ARRAY arr

#

def unboundedKnapsack(k, arr):

# Write your code here

num = False * (k+1)

for a in arr:

print(num)

for i in range(a, k+1, a):

if numi and numi + i < k+1:

num[numi + i] = True

else:

numi = True

for i in range(k+1):

if numi and numi + a < k+1:

num[numi + a] = True

for i in range(k, 0, -1):

if numi:

return i

break

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

t = int(input().strip())

for i in range(t):

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input0)

k = int(first_multiple_input1)

arr = list(map(int, input().rstrip().split()))

result = unboundedKnapsack(k, arr)

fptr.write(str(result) + '\n')

fptr.close()